如果你今天想要在一個遞增陣列裡面尋找一個值你會怎麼做呢？

一格一格找嗎？這樣的最慘的時間複雜度是O(N)（也就是找到底才找到），其實還可以更快喔。

那就要用到今天提的這個東西，二分搜，他是一個神奇的作法可以幫你在遞增序列找到數字，而且時間複雜度只要O(log N)。

簡單來說做法就是，每次把資料分半，判斷我們的資料應該屬於哪一邊。

fun findN(a: Array<Int>,N: Int):Int{
    var start = 0
    var end = a.size-1
    var mid: Int
    while (start <= end) {
        mid = (end + start) / 2
        if (a[mid] < N) {
            start = mid + 1
        }
        else if (a[mid] > N){
            end =  mid - 1
        }
        else {
            return mid
        }
    }
    return -1
}

我們透過start跟end兩個變數來設定頭尾，然後透過中間那格判斷我們應該接著往哪查，直到找到我們的值。

一定要記得，二分搜的前提是已經要排序過的序列喔。